package leetcode101.mathematical_problem;

import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code8
 * @Description 528. 按权重随机选择
 * 给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），
 * 请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。
 *
 * 例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），
 * 而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。
 *
 * 也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：
 * ["Solution","pickIndex"]
 * [[[1]],[]]
 * 输出：
 * [null,0]
 * 解释：
 * Solution solution = new Solution([1]);
 * solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。
 * 示例 2：
 *
 * 输入：
 * ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
 * [[[1,3]],[],[],[],[],[]]
 * 输出：
 * [null,1,1,1,1,0]
 * 解释：
 * Solution solution = new Solution([1, 3]);
 * solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
 * solution.pickIndex(); // 返回 1
 * solution.pickIndex(); // 返回 1
 * solution.pickIndex(); // 返回 1
 * solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。
 *
 * 由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
 * [null,1,1,1,1,0]
 * [null,1,1,1,1,1]
 * [null,1,1,1,0,0]
 * [null,1,1,1,0,1]
 * [null,1,0,1,0,0]
 * ......
 * 诸若此类。
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-26 8:46
 */
public class Code8 {
    public static void main(String[] args) {
        int[] w = new int[]{3, 14, 1, 7};
        Solution s = new Solution(w);
        s.pickIndex();
    }

    static class Solution {

        public static List<Integer> list;

//    /*
//    以下做法会超出内存限制
//     */
//    public Solution8(int[] w) {
//        list = new ArrayList<>();
//        for (int i = 0; i < w.length; i++) {
//            for (int j = w[i]; j > 0; j--) {
//                list.add(i);
//            }
//        }
//    }
//
//    public int pickIndex() {
//        int num = (int)(Math.random() * list.size());
//        return list.get(num);
//    }

        public int[] prefixSum;

        public Solution(int[] weight) {
            prefixSum = new int[weight.length];
            prefixSum[0] = weight[0];
            for (int i = 1; i < weight.length; i++) {
                prefixSum[i] = prefixSum[i - 1] + weight[i];
            }
        }

        public int pickIndex() {
            int random = (int)(Math.random() * (prefixSum[prefixSum.length - 1] + 1 - 1) + 1);
            int left = -1;
            int right = prefixSum.length;
            int mid;
            while (left + 1 != right) {
                mid = (left + right) >> 1;
                if (prefixSum[mid] < random) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            return left + 1;
        }

    }
}



/*
生成指定范围内的随机数
int num = (int)(Math.random() * (max + 1 - min) + min);
解法一是根据权重生成对应的数字
比如数字 i 的权重是 10 那么我们就生成 10 个 i
然后生成一个范围在[1, 权重和]的数组下标，返回这个下标对应的数字就行
但是这样会使内存超出限制

正确的做法是使用前缀和算法来进行空间的压缩
比如权重是[1, 3, 2]
前缀和是[1, 4, 6]
生成[1, 6]的随机数字比如说是3
然后使用二分查找确定 3 这个随机数对应前缀和的位置是1（即前缀和4所对应的下标）
然后返回权重数组对应这个下标的值。
 */